/**
 * @projectName: LeetCode
 * @package: PACKAGE_NAME
 * @className: Point4
 * @author: Mocrash
 * @description: TODO
 * @date: 2024/10/16 11:25
 * @version: 1.0
 */
public class Point5 {
    public static void main(String[] args) {
        String input = "a";
        Solution solution = new Solution();
        String longestPalindrome = solution.longestPalindrome(input);
        System.out.println("最长回文串是: " + longestPalindrome);
    }

    private static class Solution {

        public String longestPalindrome(String s) {
            boolean[][] dp = initDp(s.length());

            char[] charArray = s.toCharArray();
            int maxLength = 0, maxStartIndex = -1, maxEndIndex = -1;
            for (int i = 0; i < charArray.length; i++) {
                int front = i, back = i;
                while (front >= 0 && back < charArray.length) {
                    if (front == back) {
                        if (maxLength < back - front + 1) {
                            maxStartIndex = front;
                            maxEndIndex = back;
                            maxLength = back - front + 1;
                        }
                        dp[front][back] = true;
                        front -= 1;
                        back += 1;
                        continue;
                    }
                    if (dp[front + 1][back - 1] == true && charArray[front] == charArray[back]) {
                        dp[front][back] = true;
                        if (maxLength < back - front + 1) {
                            maxStartIndex = front;
                            maxEndIndex = back;
                            maxLength = back - front + 1;
                        }
                        front -= 1;
                        back += 1;
                    } else {
                        break;
                    }
                }
                if (i == charArray.length - 1){
                    break;
                }
                front = i;
                back = i + 1;
                while (front >= 0 && back < charArray.length) {
                    if (front + 1 == back ) {
                        if (charArray[front] != charArray[back])break;
                        dp[front][back] = true;
                        if (maxLength < back - front + 1) {
                            maxStartIndex = front;
                            maxEndIndex = back;
                            maxLength = back - front + 1;
                        }
                        front -= 1;
                        back += 1;
                        continue;
                    }
                    if (dp[front + 1][back - 1] == true && charArray[front] == charArray[back]) {
                        dp[front][back] = true;
                        if (maxLength < back - front + 1) {
                            maxStartIndex = front;
                            maxEndIndex = back;
                            maxLength = back - front + 1;
                        }
                        front -= 1;
                        back += 1;
                    } else {
                        break;
                    }
                }

            }
            return String.valueOf(charArray, maxStartIndex, maxEndIndex - maxStartIndex + 1);
        }

        private boolean[][] initDp(int strLength) {
            boolean[][] dp = new boolean[strLength][strLength];
            return dp;
        }

    }
}

